8.1.1 פעולות בעץ אדום-שחור

מבנה נתונים ואלגוריתמים

 

 

 זוהי דוגמא לפעולת הכנסה בעץ אדום-שחור:

 

 

 

זהו העץ המקורי. שים לב כי בדיאגרמות הבאות,

הצמתים התחתונים הושמטו על מנת להשאיר

את הדיאגרמות פשוטות.

 

 

 

 

 

 

 

 

 

כעת נקרא לשגרת ההכנסה של העץ על מנת

להכניס את צומת "4" לתוך העץ.

 

כעת העץ אינו עוד עץ אדום-שחור

-          יש שני צמתים אדומים רצופים בנתיב

 4 - 5 - 7 - 2 - 11.

 

נסמן את הצומת החדש כ- x, ואת דודו כ- y.

y הוא אדום, לכן נקבל את מקרה 1 ...

 

 

 

 

 

 

נשנה את הצבעים של צמתים 4, 7 ו- 8.

 

 

 

 

 

 

 

 

 

 

 

 

 

נעביר את x למעלה, לסבו 7.

אביו של x (2) עדיין אדום,

ולכן עדיין אין זה עץ אדום-שחור.

נסמן את הדוד, y. במקרה זה הדוד הוא שחור,

ולכן נקבל את מקרה 2...

 

 

 

 

 

 

 

 

 

 

 

נעביר את x כלפי מעלה ונסובב כלפי שמאלה.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

עדיין אין זה עץ אדום-שחור... הדוד הוא שחור, אך

אביו של x הוא משמאל ...

 

 

 

 

 

 

 

 

 

 

 

 

 

נשנה את הצבעים של 7 ו- 11 ונסובב ימינה...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

סיימנו! כעת זהו עץ אדום-שחור.

 

 

 

 

 

 

 

 

הפעולה דרשה בסך הכל זמן של O(logn).

 

 

חזור ל: עצי אדום-שחור                 חזור ל: תוכן עניינים